九州大学学術情報リポジトリ
Kyushu University Institutional Repository
バッファ・オーバフロー・アタックを動的に検出す るセキュア・キャッシュ—安全性と消費エネルギー のトレードオフ—
井上, 弘士
科学技術振興機構さきがけ | 福岡大学工学部電子情報工学科
http://hdl.handle.net/2324/6121
出版情報：先進的計算基盤システムシンポジウム (SACSIS2004), pp.315-323, 2004-05 バージョン：
権利関係：
バッファ・オーバフロー・アタックを動的に検出するセキュア・キャッシュ
―安全性と消費エネルギーのトレードオフ―
井上弘士 †‡
A Secure Cache Architecture against Buffer-Overflow Attacks - Considering an Energy - Security Tradeoff -
K OJI I NOUE
†
‡
†
福岡大学工学部電子情報工学科 〒814-0133 福岡県福岡市城南区七隈 8-19-1‡
科学技術振興機構さきがけ 〒332-0012 埼玉県川口市本町4丁目1番8号1. はじめに
近年，
LSI
技術やネットワーク技術の発展に伴い，例えばユビキタス・コンピューティングのように便 利で快適な社会環境が現実となりつつある．そして，
電子財布や電子マネー，さらには，電子投票といっ た様々なデジタル・サービスの普及に伴い，コンピ
ュータ・システムは今まで以上に重要かつ秘密性の 高い情報を処理するようになるであろう．したがっ て，安心して暮らせる高度情報化社会を実現するた めには，コンピュータ・システムの安全性向上が必 要不可欠となる．
一方，1970 年代初頭にマイクロプロセッサが開 発されて以来，それを核とするコンピュータ・シス 本稿では，高度情報化社会システムの大きな脅威であるコンピュータ・ウィルス問題に着目し，
それを解決するアーキテクチャ・アプローチとしてセキュア・キャッシュ(SCache)を提案する．
また，このようなキャッシュ・システムを前提とし，安全性と消費エネルギーのトレードオフに 関する議論を行う．多くのコンピュータ・ウィルスはバッファ・オーバフローを引き起こし，関 数の戻りアドレスを改ざんすることでプログラムの実行制御を乗っ取る．SCache では，本来キ ャッシュが有する冗長性を活用し，書込みデータの複製を生成することで戻りアドレスを保護す る．ベンチマーク・プログラムを用いた定量的評価を行った結果，多くのプログラムにおいて 99.7%以上の戻りアドレスの安全性を保障することができた．
This paper proposes a novel cache architecture, called Secure Cache (SCache), to protect computer systems from malicious codes, and discuses an energy-security tradeoff. A number of malicious codes attempt to take program-execution flow by causing stack smashing that corrupts a return address. In order to avoid the return address corruption, SCache generates a replica data in the cache area. In our evaluation, for many benchmarks, it is observed that more than 99.7% of return-address loads can be protected.
テムは目覚しい性能向上を遂げてきた．その中でも 特に，拡大を続けるプロセッサ―主記憶間の性能差 を隠蔽するため，キャッシュ・メモリは重要な役割 を担っている．そして，高いヒット率と高速アクセ スの両立を目指し，これまでに多くの研究/開発が 行われた[2][8]．また，1990 年代におけるモバイ ル・コンピューティングの普及に伴い，高性能化と 低消費電力化といった相反する要求を同時に満足 する様々なキャッシュ・アーキテクチャが提案され てきた[6][7][9][11]．しかしながら，安全性の向上 に関する議論は殆ど行われていないのが現状であ り，今後はセキュリティを考慮したメモリ・システ ムの実現方式を確立する必要がある．
そこで本稿では，コンピュータ・システムの安全 性向上を目的とした新しいキャッシュ・アーキテク チャとしてセキュア・キャッシュ(
SCache )を提案す
る．具体的には，コンピュータ・ウィルス問題に着 目し，最近特に多くの被害が報告されているバッフ ァ・オーバフロー・アタックの動的検出方式を示す．また，安全性だけでなく，性能や消費エネルギーに 関する考慮も必要である．そこで本稿では，これま でには殆ど行われていない安全性と消費エネルギ ーのトレードオフに関して議論する．
以下，第
2
節ではバッファ・オーバフローによる スタック・スマッシングの詳細を説明する．また，これまでに提案された安全性向上技術を紹介し，提 案手法との違いを明確にする．次に，第
3
節ではSCache
アーキテクチャの内部構成ならびに動作の詳細を示し，第
4
節で安全性と消費エネルギーに関 する評価を行う．そして，最後に第5
節で簡単にま とめる．2. スタック破壊によるプログラム実行の乗っ取り
2.1 被害状況
近年，バッファ・オーバフローの脆弱性を活用し た悪質プログラムによる被害が急増している．例え ば，代表的なものとして
2001
年に猛威を振ったCode Red
や，2003
年のBlaster
などがある． 悪 質プログラムは，攻撃対象となるコンピュータが正 規アプリケーションを実行している最中にバッフ ァ・オーバフローを引き起こさせ，強制的にプログ ラムの実行制御を乗っ取る．したがって，特権モー ドでの実行中にバッファ・オーバフローが発生した 場合，悪質プログラムは特権モードで実行されるこ とになる．その結果，ファイルの削除や改ざんが可 能となり多大なる被害をもたらす．CERT
によって 発せられた勧告(1996〜2001 年)の内，バッファ・オーバフローに関連するものの割合を図 1に示す．
図から分かるように，多くの悪質プログラムはバッ ファ・オーバフローの脆弱性を利用しており，その 防御策が極めて重要となる．
2.2 スタック・スマッシング
悪質プログラムは，関数呼び出し後にバッファ・
オーバフローを引き起こしてスタックを破壊する
(スタック・スマッシング)．そして，関数呼出し側
への戻りアドレスを悪質プログラム・コードの先頭 アドレスへと改ざんすることで，プログラムの実行 制御を乗っ取る．このようなスタック・スマッシン グの原因となるバッファ・オーバフローの脆弱性は，strcpy
やstrcat
などのC
標準ライブラリ内に存在 する．これらの関数では，文字列をローカル変数に 代入する際に領域サイズのチェックを行わない．そ のため，ローカル変数で指定したバッファ・サイズ より大きな文字列等を代入した場合，確保されたロ 010 20 30 40 50 60
1996 1997 1998 1999 2000 2001 バッファ・オーバフローに関連する 勧告の割合(%)
図 1：CERTバッファ・オーバフロー勧告(文献[1])
図
2
：スタック・スマッシング s1戻りアドレス
FP退避
ローカル変数
buf FP
SP
上位アドレス
下位アドレス スタックの
伸張
int f ( ) { … g (s1);
… }
int g ( char *s1) { char buf [10];
… strcpy(buf, s1);
… }
プログラム・コード例
s1
改ざんされた 戻りアドレス
悪質コード
FP
SP
関数呼出し時の スタック
スタック スマッシング
ーカル変数メモリ領域の境界を越えて書込みを行 う．
スタック・スマッシング発生時の様子を図 2に示 す．ここでは，
strcpy
を用いて文字列コピーを行う 関数g
が，関数f
によって呼出される場合を想定し ている．通常，関数g
が呼出された際，関数f
への 戻りアドレスをスタックに保存する．そして，関数g
での処理終了後，この戻りアドレスをPC
に復元 する事で関数呼出し側へと実行制御が移る．これに 対し，バッファ境界をチェックしない文字列コピー によりスタック・スマッシングが発生した場合，ス タック領域に対して悪質プログラム・コードが上書 きされる．また，関数f
への戻りアドレスが悪質コ ードの先頭アドレスへと改ざんされる．その結果，呼出し元関数
f
へ復帰する際には改ざんされた戻り アドレスが用いられ，その結果としてスタック内部 の悪質プログラム・コードへと実行制御が移る．2.3 関連研究
これまでに，スタック・スマッシングに対する 様々な防御方法が提案された．これらは，バッフ ァ・オーバフロー回避のためのコード解析や変換の 有無，ならびに，スタック・スマッシングの検出時 期によって以下のように分類できる．
• 静的解析かつ静的検出型：プログラム・コードを 静的に解析してバッファ・オーバフロー発生可能 場所を検査する．例えば，文字列操作に限定し，
「コピー元の文字列サイズ」が「コピー先のロー カル変数領域サイズ」を超えていないか検査する 方法などがある[13]．
• 静的解析
/
変換かつ動的検出型：プログラムの静 的解析により，スタック・スマッシングを検出す るためのコード変換をコンパイル時に行う．文献[4]で提案された SASI
では，実行の振舞いを監視 するリファレンス・モニタ(RM)をコード中に挿 入する．例えば，バッファ・オーバフローの危険 性があるコード部分に対し，領域チェックを行う ためのRM
コードを挿入する．また，文献[3]
で 提案されたStackGuard
では，canary word
と呼 ばれる乱数を生成して戻りアドレスと共にスタ ックへ格納する．canary は戻りアドレスの直後 にプッシュされるため，スタック・スマッシング が発生した場合にはcanary
値も改ざんされる．よって，関数呼出し時と復帰時の
canary
値を比 較する事で戻りアドレスの改ざんを検査できる．• 動的解析/変換かつ動的検出型：プログラム実行 中にコードの解析や変換を行う．先に説明した静 的解析や変換を行う方式とは異なり，オブジェク ト・コードの互換性を保つ事ができる．具体的に は，バイナリ変換を行うことで，リファレンス・
モニタに相当するバッファ・オーバフロー検査用 コードを動的に生成する方法などがある[1][12]．
• 解析/変換を必要としない動的検出型：コード解 析や変換を行う事無く，戻りアドレス保護を実現 する方式である．ソフトウェア・アプローチとし ては，安全性を保障した
C
ライブラリ(libsafe
と 呼ばれる)を提供する方法や，OS
の介在により動的に
canary
を追加する方法などが提案されている[1][5]．一方，ハードウェア・アプローチとし ては，プロセッサ内部に戻りアドレス専用スタッ クである
SRAS(Secure Return Address Stack)
を搭載する方法が提案されている[10]
．戻りアド レスをプッシュする際，それと同時にSRAS
に も戻りアドレスを書込む．そして，関数から復帰 する時，メモリ・スタックならびにSRAS
から ポップした戻りアドレスを比較する．比較結果が 不一致であればスタック・スマッシングが発生し ていることになる．本稿で提案する
SCache
は「解析/変換を必要と しない動的検出型」のハードウェア・アプローチに 属する．したがって，オブジェクト・コードの互換 性を完全に保つ事ができる．また，C
ライブラリやOS
といったシステム・ソフトウェアの変更は伴わ ない．SCacheの基本アプローチは，SRASと同様 に戻りアドレスをメモリ・スタックとは別領域に保 存しておき，関数からの復帰時に比較することでス タック・スマッシングを検出する．しかしながら，SRAS
は小容量スタック・メモリとしてプロセッサ 内部に実装される．そのため，関数呼出しのネスト に伴い容量が不足した場合には，保護された安全な 主記憶領域との間でエントリの追出し/リフィルが 行われる．SCacheも同様の問題を有するが，キャ ッシュ・メモリという大容量記憶領域を使用するた め，より多くの戻りアドレスをプロセッサ・チップ 内部で保護できる．また，SRAS
とは異なり，LIFO
動作と異なる関数制御(例えばsetjmp
やlongjmp)
の場合でもソフトウェアの介在無しに対応できる．さらに，提案手法はプロセッサの内部構造に殆ど影 響を与えないため，アウト・オブ・オーダ実行や高
度な分岐予測機構を搭載した複雑なプロセッサに 対しても容易に適用可能である．
3. セキュア・キャッシュ・アーキテクチャ 3.1 基本アイデア
通常，関数呼出し時にスタック領域へプッシュさ れる戻りアドレスは，一旦キャッシュにストアされ る．また，呼出し元関数へ復帰する際，プロセッサ はキャッシュから戻りアドレスをポップする．スタ ック・スマッシングによるプログラム制御の乗っ取 りにおいて，その本質的な問題点は戻りアドレスが 改ざんされることにある．したがって，キャッシュ 上での戻りアドレス保護が可能であれば，プロセッ サ構造に影響を与えることなくバッファ・オーバフ ロー問題を解決できる．そこで
SCache
では，戻り アドレスがストアされる際，読出し専用の複製ライ ン(レプリカ・ラインと呼ぶ)を同一セット内に作成 する(
最大で「連想度−1
個」のレプリカ・ラインを 生成可能)
．その後，戻りアドレスをロードする時，スタック領域から読出される値と，レプリカ・ライ ンの値を比較する．もし，比較結果が一致であれば 戻りアドレスの安全性が保障され，不一致の場合に はスタック・スマッシングの発生を検出する．
3.2 内部構造と動作
連想度が
4
のSCache
内部構造を図 3に示す．戻 りアドレスの書込み当たりに生成されるレプリ カ・ライン数(Nrep)
は2
と仮定している．SCache
では，全てのタグ・エントリに対して1
ビットのレ プリカ・フラグ(Rフラグ)を追加する．これは，対 応するキャッシュ・エントリがレプリカ・ラインで あるか否かを示すフラグである．また，従来の一般的なキャッシュ構造に加え，レプリカ・ライン専用 マルチプレクサ(Replica-MUX)と制御信号生成回 路 ， な ら び に ，32 ビ ッ ト 比 較 回 路(Word-Data
Match)が必要となる． SCache
のアクセス動作を図4に示す．ここではキャッシュ・ヒットの場合を想
定しているが，ミスの場合でもライン・リプレイス が発生することを除いて基本的に同じである．プロ グラム実行において戻りアドレスをストアする際，SCache
は以下のように動作する．1.
従来型キャッシュと同様，参照アドレス中のイ ンデックスを用いてアクセス対象セット(参照 セットと呼ぶ)
を決定する．そして，タグ比較 を行い，ヒットしたラインに戻りアドレスを書 込む(このラインをマスタ・ラインと呼ぶ)．2.
参照セットにおいて，同一タグを有するレプリ カ・ラインがすでに存在する場合にはストアす る戻りアドレスで上書きする．つまり，存在す るレプリカ・ラインを更新してコヒーレンシ問 題の発生を回避する．3.
参照セットにおいて，レプリカ・ライン数がNrep
となるまでレプリカ・ラインを生成する．また，対応する
R
フラグをセットする．一方，呼出し元関数への復帰時に戻りアドレスが ロードされる際，
SCache
は以下のように動作する．1.
参照セットから全ラインとタグを読出す．そし て，タグ比較結果が一致しており，かつ，Rフ ラグがリセットされているライン(つまりマス タ・ライン)
を選択してプロセッサにデータを 転送する．2.
タグ比較結果が一致しており，かつ，R
フラグ 図3
：SCache
の内部構成ML RL RL
way0 way1 way2 way3
tag data
Data (Ret. Addr.)
Load (pop)
Replica-MUX
Safe?
replica replica
Read-MUX master
Tag Match
&& R-flag Tag Match
&& no R-flag
HIT?
Word-Data Match Ref. Addr.
Index
Tag Offset
Store (push)
Data (Ret. Addr.)
RL: Replica Line ML: Master Line
図 4：SCacheの動作(ヒット時)
キャッシュ・アクセス
（戻りアドレス）
Store?
yes
戻りアドレスをMLへストア
RL数＝Nrepとなるまで新 規RLを作成
正常終了
Store
noLoad
全てのウェイからラインを読出し (MLから戻りアドレス値を出力)
yes
危険正常終了
no
安全正常終了 同一タグのRLが存在する
場合は上書き RLヒット(タグ比較)
no
yes
戻りアドレス一致
危険異常終了
RL: Replica Line ML: Master Line
がセットされているライン(つまりレプリカ・
ライン)が複数存在する場合は何れか
1
つを選 択する．もし，レプリカ・ラインが存在しない 場合はロードされる戻りアドレスの安全性を 保障できないため，その旨をプロセッサに通知 してアクセスを終了する．3. コピー元であるマスタ・ラインの戻りアドレス
と，選択したレプリカ・ラインのそれを比較す る．もし，比較結果が不一致であればスタッ ク・スマッシングが発生しており，その旨をプ ロセッサに通知してアクセスを終了する．実際には，戻りアドレスの書込みと同時にレプリ カ・ラインを生成する．また，戻りアドレスの読出 し時，アクセス・データやヒット信号の生成/出力 は従来キャッシュと同様の手順となる．さらに，プ ロセッサは当該ロードが安全である事を示す
safe
信号を待つ必要は無い(悪質コードに制御が移る前 までに検出されれば良い)．したがって，SCache
方 式によるキャッシュ・アクセス時間の増加は殆ど発 生しない．一方，戻りアドレスを操作対象としない 通常のロード/
ストアは，マスタ・ラインに対して のみ実行される(
ヒット条件にはR
フラグがリセッ トされていることが含まれる)．よって，レプリカ・ラインに格納した戻りアドレスの複製が通常スト アによって更新されることは無い．なお，SCache を実装する場合，発行されたロード/ストア命令が 戻りアドレスを対象とする事を示す情報をプロセ ッサから入力しなければならない．通常，戻りアド レスは固定レジスタへ保存される(例えばR31)ため，
プロセッサではこのレジスタを対象とするロード/
ストアであることを
SCache
に通知するだけでよ く，そのための回路変更は極めてわずかである．3.3 安全性と消費エネルギーに関する欠点
SCache
では，関数呼出し時と復帰時の戻りアドレスそのものを比較し，その結果が一致である場合に は戻りアドレスの安全性を保障する．しかしながら，
レプリカ・ラインは通常のラインと同様，キャッシ ュ内競合が発生した場合には置換えの対象となる．
そのため，全てのレプリカ・ラインがキャッシュか ら追出された場合には、戻りアドレスの改ざんを検 出することができない。
一方，消費エネルギーに関して，
SCache
は主に3
つの欠点を有する．1つめはキャッシュ・アクセ ス消費エネルギーの増加である．これまでに提案された多くの低消費電力キャッシュでは，メモリ参照 で必要となるデータにのみアクセスする事で低消 費エネルギー化を実現する[6][11]．しかしながら，
SCache
では，戻りアドレスの読出し/書込みを行うと同時に，レプリカ・ラインの読出しや書込みが必 要となる．その結果，本来は必要としないメモリ・
アレイの活性化が発生し多くのエネルギーを消費 する．第
2
の欠点は，下位階層メモリ・アクセスに おける消費エネルギーの増大である．レプリカ・ラ イン数の増加に伴い，有効なキャッシュ容量は小さ くなる．その結果，L1
キャッシュのヒット率が低 下し，下位メモリ階層へのアクセス回数(例えばL2
キャッシュ・アクセス回数)が増加する．そして第3
の問題点は，ラインのライトバックに伴う消費エネ ルギーの増大である．SCacheにおいてレプリカ・ラインを作成する際，参照セット内に空き領域が無 い場合は何れかのラインをキャッシュから追出す 必要がある．もし，追出し対象ラインの状態がダー ティーである場合にはライトバックが必要となる．
レプリカ・ラインの追出しに関する問題を回避す る手段として，複数レプリカ・ラインの作成や，
MRU
アルゴリズムに基づく配置(
マスタ・ライン を除くMRU
ライン)
が挙げられる．つまり，レプ リカ・ラインのキャッシュ滞在時間をより長くする ことで安全性を向上する．また，より安全性を重視 する場合，レプリカ・ラインの追出しそのものを禁 止する方法も考えられる．しかしその反面，これら はキャッシュ・ヒット率の低下を引き起こし，消費 エネルギーに関する欠点をより顕著にする可能性 がある．4. 評価
4.1 実験環境
提 案 方 式 の 有 効 性 を 評 価 す る た め ，
SimpleScalar
ツールセットVer.3.0d
を改良してSCache
を実装した[14]．また，SPEC2000ベンチ マーク・サイトより7
つの整数プログラムと4
つの 浮動小数点プログラムを用いてOOO
実行のサイク ルレベル・シミュレーションを行った[15]
．入力デ ータとしてはSPEC
より提供されるsmall input
を使用している．L1 データ・キャッシュ・サイズ は16KB，ラインサイズは 32B，連想度は 4
と仮定 し，その他のプロセッサ構成に関する詳細なパラメ ータはSimplescalar
のデフォルト値を用いた．SCache
では，戻りアドレスがロードされる時，レプリカ・ラインが存在する場合には安全性を保障 できる．本稿では，以下の式で安全性を評価する．
Vulnerability = (Nv-rald / Nrald) * 100 (1)
ここで，
Nrald
はプログラム実行におけるIRA
ロードの総数である．ここで
IRA(Issued Return Address)ロードとは，キャッシュ・メモリに対して
発行された戻りアドレス・ロードの事である．また，Nv-rald
は戻りアドレス改ざんを検出できない(安全性を保障できない
)IRA
ロード総数を示す．一方，消費エネルギーに関しては以下の式で評価する．
Etotal = Erd + Ewt + Ewb + Emp (2)
ここで，Erd
とEwt
は，それぞれ，L1キャッシュ の読出し/書込み総消費エネルギーである．また，Ewb
はレプリカ・ラインの作成に伴うライトバッ ク総消費エネルギーを表す．さらに，Emp
はキャ ッシュ・ミス発生において消費されるエネルギーを 示す．実際には，0.18 μm CMOS
プロセスを用いて1ウェイ分(4KB)のSRAMアレイのレイアウト設計
ならびに負荷容量抽出を行い，プリチャージ動作も 含めた1
ビット当たりの読出し/書込み消費エネル ギーを測定した．また，その結果に基づき，キャッ シュ・アクセスにおける消費エネルギーを換算した．なお，
Emp
の値はメモリ階層構造に大きく依存す る．そこで，1回の下位メモリ階層アクセスに要す るエネルギーは，従来型キャッシュにおける平均読 出し消費エネルギーの10
倍と仮定した．4.2 実験結果（安全性）
本評価ではキャッシュの連想度を
4
と仮定して いるため，LRUまたはMRU
アルゴリズムに基づ き最大3
個のレプリカ・ラインを生成可能である．そこで，これらの組合せに関して安全性を評価した．
実験結果を図 5に表す．また，従来キャッシュ
(CONV)におけるミス率と IRA
ロード数(Nrald )，
ならびに，各
SCache
モデルにおけるミス率を表 1 に示す．ここで，LRU1RならびにLRU2R
は，そ れぞれ，LRU
配置アルゴリズムに基づき1
個もし くは2
個のレプリカ・ラインを生成するモデルであ る．同様に，MRU1RとMRU2R
は配置アルゴリ ズムにMRU
方式を用いている．ALLは，参照セ ット中の全ライン(ただし，マスタ・ラインを除く) にレプリカ・ラインを生成する．本シミュレーションでは
L1
キャッシュ・ミス時 のライン置換えアルゴリズムにLRU
方式を採用し ている．そのため，LRU1Rで作成したレプリカ・ラインは他アクセスによって容易にキャッシュか ら追出される．これに対し，
LRU2R
ではレプリカ・ラインのキャッシュ生存期間が長くなるため，より 高い安全性を実現している．また，同様の理由によ り，MRU方式の採用によっても安全性は向上して いる．全ての
SCache
モデルを比較した場合，ALL
が最も高い安全性を達成しており，多くのプログラ ムで99.7%
以上のIRA
ロードの安全性を保障する ことができた．一方，表 1で示すように，生成する レプリカ・ライン数の増加，または，MRU方式の 採用に伴い，キャッシュ・ミス率が高くなっている．したがって，性能を重視する場合には，ミス率の低 下と安全性の向上を考慮して
MRU1R
を選択する ことが適切であると考える．なお，SCacheでの戻 りアドレス書込み時，第3.2節で説明したように，同一タグを有するレプリカ・ラインがすでに存在す る場合にはそれらへの上書きを行う．よって，
LRU
領域にこのようなレプリカ・ラインが存在する場合，MRU1R
はLRU1R
と同じ動作となる．そのため，MRU
方式においても，作成されるレプリカ・ライ ン数を増加することで安全性が向上する．4.3 実験結果(消費エネルギー)
第
4.1
節で示した消費エネルギー・モデルに基づ き評価した結果を図 6に示す．ここで，図 6は，不 必要なウェイ・アクセスを回避するウェイ予測キャ ッシュ[6]を基準とした際の消費エネルギー・オー バヘッドを表している．この図から，レプリカ・ラ イン数の増加に伴いオーバヘッドが大きくなって いる事が分かる．特に，最も多くのレプリカ・ライ ンを生成するALL
では，最大で約23%の消費エネ
ルギー・オーバヘッドが発生した(197.parser )．
図 5：危険な戻りアドレス・ロードの発生率
0.0%
0.5%
1.0%
1.5%
2.0%
2.5%
3.0%
164.gzip 175.vpr
176.gcc 181.mcf
197.parser 255.vortex
256 .bzip
177.mesa 179.art
183.equake 188.ammp
Benchmarks
Vulnerability
LRU1R LRU2R MRU1R MRU2R ALL
5.4%
0.0%
0.5%
1.0%
1.5%
2.0%
2.5%
3.0%
164.gzip 175.vpr
176.gcc 181.mcf
197.parser 255.vortex
256 .bzip
177.mesa 179.art
183.equake 188.ammp
Benchmarks
Vulnerability
LRU1R LRU2R MRU1R MRU2R ALL LRU1R LRU2R MRU1R MRU2R ALL
5.4%
表
1
：キャッシュ・ミス率 CONVModel
Bench. Miss Rates #IRA Load(Nrald) LRU1R LRU2R MRU1R MRU2R ALL
164.gzip 5.22% 4,930,467 5.22% 5.22% 5.22% 5.23% 5.25%
175.vpr 3.53% 5,627,709 3.56% 3.63% 3.59% 3.66% 3.74%
176.gcc 4.26% 37,519,156 4.29% 4.37% 4.33% 4.43% 4.64%
181.mcf 20.02% 992,419 20.02% 20.03% 20.05% 20.06% 20.10%
197.parser 4.13% 45,466,527 4.18% 4.44% 4.23% 4.55% 5.07%
255.vortex 1.75% 22,101,265 1.79% 1.91% 1.82% 1.94% 2.32%
256.bzip 2.31% 18,147,017 2.31% 2.32% 2.31% 2.32% 2.45%
177.mesa 0.14% 4,727,396 0.15% 0.16% 0.15% 0.16% 1.08%
179.art 42.93% 32,466 42.93% 42.93% 42.93% 42.93% 42.93%
183.equake 2.44% 3,580,827 2.44% 2.46% 2.45% 2.47% 2.52%
188.ammp 36.27% 6,307,839 36.28% 36.31% 36.28% 36.30% 36.38%
IRA: Issued Return Address
消費エネルギーを詳細に解析するため，第4.1 節で示した式
(2)
に関する内訳を測定した．その結 果を図7
に示す．ここでは，紙面の都合上，消費エ ネルギー・オーバヘッドが最も大きな2
つの整数プ ログラム(197.parser，255.vortex )と浮動小数点プ
ログラム(177.mesa，183.equake )，ならびに，最
も オ ー バ ヘ ッ ド が 小 さ い2
つ の プ ロ グ ラ ム( 181.mcf
，179.art )
での結果を示している．従来キ ャッシュ(CONV)と比較して，読出し消費エネルギ ーErd
は全てのSCache
モデルにおいてほぼ同じ増 加率である．これは，レプリカ・ライン作成数なら びに配置アルゴリズムに関わらず，戻りアドレス・ロード発行時に全てのウェイが活性化されるため である．反対に，書込み消費エネルギー
Ewt
は作成 されるレプリカ・ライン数に比例して増加する．ま た，Emp
はミス率の増加に伴い大きくなっている．特に
177.mesa
において，従来方式と比較した場合，ALL
モデルは大幅なヒット率の低下を引き起こしており
(
表1
を参照)
，その影響によるEmp
の増加 が顕著に現れている．オーバヘッドの小さい
181.mcf
ならびに190.art
とその他を比較した場合，これら2
つのプログラム ではキャッシュ・ミスによる消費エネルギーが多く の割合を占めている．実際，表1
で示すように，こ れらプログラムのミス率は極めて高い．このように，従来のミス率と比較して，SCacheによるミス率の 増加が十分小さい場合，
Emp
に関する消費エネル ギー・オーバヘッドが隠蔽される．また，本評価で 基準としているウェイ予測方式では，ミス率の増加 と共にウェイ予測による消費エネルギー削減効果 が低減する．これらの理由により，SCache
の採用 に伴う消費エネルギー・オーバヘッドは小さくなっ たものと考える．一方，全てのプログラムにおいて，LRU1R と
MRU1R， LRU2R
とMRU2R
をそれぞれ比較した0%
5%
10%
15%
20%
25%
164 .gzip
175.vpr 176.gcc
181.
mcf 197.
parser 255.
vortex 256
.bzip 177.mesa
179 .art
183.equake 188.
amm p Benchmarks
Energy Overhead
LRU1R LRU2R MRU1R MRU2R ALL
0%
5%
10%
15%
20%
25%
164 .gzip
175.vpr 176.gcc
181.
mcf 197.
parser 255.
vortex 256
.bzip 177.mesa
179 .art
183.equake 188.
amm p Benchmarks
Energy Overhead
LRU1R LRU2R MRU1R MRU2R ALL LRU1R LRU2R MRU1R MRU2R ALL
図 6：消費エネルギー・オーバヘッド
0 0.2 0.4 0.6 0.8 1 1.2 1.4
181.mc f
197.parser 255.vortex
177.mesa 179.art
183.equake
Benchmarks
Normalized Energy
Emp Ewb Ewt Erd CONV LRU1R LRU2R MRU1R MRU2R ALL
0 0.2 0.4 0.6 0.8 1 1.2 1.4
181.mc f
197.parser 255.vortex
177.mesa 179.art
183.equake
Benchmarks
Normalized Energy
Emp Ewb Ewt Erd Emp Ewb Ewt Erd CONV LRU1R LRU2R MRU1R MRU2R ALL
図 7：消費エネルギーの内訳
場合，消費エネルギーに関する差は殆ど見られない．
生成するレプリカ・ライン数が同じ場合，配置アル ゴリズムには関係なくキャッシュ消費エネルギー はほぼ同一となる．これに対し，MRU方式の場合 はヒット率の低下を招くが，それによる消費エネル ギー・オーバヘッドが比較的小さかった．このよう な結果を考慮し，レプリカ・ラインの配置アルゴリ ズムには
MRU
方式が適していると考える．4.4 実験結果（性能）
SCache
ではレプリカ・ラインをキャッシュ内セットに生成するため，キャッシュ・ミス率の増加に 伴う性能オーバヘッドが生じる．各ベンチマークに おける性能オーバヘッドを図 8に示す．生成するレ プリカ・ライン数が最大である
ALL
モデルにおい て，最悪の場合でも性能低下は1.1%( 177.mesa )で
ある．また，その他のモデルに関しては，197.paser
を除く全てのプログラムにおいて0.2%以下の性能
オーバヘッドである．これは，保護すべき戻りアド レスの数に対し，データキャッシュは十分な容量を 有するためである．以上より，提案手法による性能 低下は無視できる程度に小さいと考える．5. おわりに
本稿では，スタック・スマッシングに対するアー キテクチャ・アプローチとしてセキュア・キャッシ ュ(SCache)を提案した．SCacheでは，キャッシュ の大容量領域を活用して戻りアドレスを保護する．
実験を行った結果，多くのプログラムで
99.7%以上
の戻りアドレス・ロードに関して安全性を保障する ことができた．また，消費エネルギー解析を行った 結果，安全性を重要視する場合には全てのラインに 複製を生成するALL
モデルが，一方，ある程度の安全性を維持しつつ低消費エネルギー化が要求さ れる場合には
MRU
方式に基づくMRU1R
が適切 であると分かった．本稿での提案手法は完全ハードウェアによるバ ッファ・オーバフロー解決手段の一つである．この ような方式においてはハードウェアの追加または 変更が必要であるため，今日主流となっている「ソ フトウェアの更新」と比較して，既存計算機システ ムへの適用可能性は低くなる．しかしながら，依然 としてバッファ・オーバフローを活用した不正プロ グラムは猛威を振るっており，特に重要な情報を処 理対象とする次世代電子機器システムではその開 発時に安全性を考慮する必要がある．よって，本稿 での提案は安全性を考慮した次世代計算機システ ムの構築における
1
つのアプローチと位置づける ことができる．本実験では，主に性能測定を目的として使用され る
SPEC
ベンチマークを利用した．今後，実際に バッファ・オーバフローの脆弱性を有するプログラ ムを用いた評価が必要である．また，様々なキャッ シュの構成を前提としたより詳細な性能，消費エネ ルギー，ならびに，安全性に関する評価を行い，こ れらの間に存在するトレードオフの探索ならびに 最適化技術を開発する予定である．なお，現在，0.18
μm CMOSプロセスを用いたSCache
コアの完全 版を設計中である．謝辞
本研究を遂行するにあたり，多くのご意見を頂い た科学技術振興機構さきがけプロジェクト「情報基 盤と利用環境」領域関係者各位に感謝します．また，
様々な議論を共にした福岡大学モシニャガ研究室 ならびに九州大学安浦研究室の諸氏に感謝する．な お，本設計は東京大学大規模集積システム設計教育 研究センターを通し，株式会社日立製作所および大 日本印刷株式会社の協力で行われたものである．
参 考 文 献
[1] A.Baratloo, N.Singh, and T.Tsai, “Transparent Run-Time Defense Against Stack Smashing Attacks,” Proc. of 2000 USENIX Annual Technical Conference, June 2000.
[2] J.-L. Baer, "2K papers on caches by Y2K: Do we need more?,” KeyNote Address in the 6th Int. Symp. on High-Performance Computer Architecture, Jan. 2000.
http://www.irit.fr/ACTIVITES/EQ_APARA/HPCA6/Ba erHpca6.PDF
[3] C.Cowan, C.Pu, D.Maier, H.Hinton, J.Walpole, P.Bakke,
図 8：性能オーバヘッド
0 .0 % 0 .2 % 0 .4 % 0 .6 % 0 .8 % 1 .0 % 1 .2 % 1 .4 %
164.gzip 175.vpr
176.gcc 181.mcf
197.
parser 255.vortex
256.bzip 177.mesa
179 .art
183.equake 188.
ammp Be n ch marks
Performance Overhead
LRU1R LRU2R MRU1R MRU2R ALL
0 .0 % 0 .2 % 0 .4 % 0 .6 % 0 .8 % 1 .0 % 1 .2 % 1 .4 %
164.gzip 175.vpr
176.gcc 181.mcf
197.
parser 255.vortex
256.bzip 177.mesa
179 .art
183.equake 188.
ammp Be n ch marks
Performance Overhead
LRU1R LRU2R MRU1R MRU2R ALL LRU1R LRU2R MRU1R MRU2R ALL
S.Beattie, A.Grier, P.Wagle, and Q.Zhang, “StackGuard:
Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks,” Proc. of 7th USENIX Security Symposium, Jan, 1998.
[4] U.Erlingsson and F.B.Schneider, “SASI Enforcement of Security Policies: A Retrospective,” Proc. of the workshop on New security paradigm, 1999.
[5] M.Frantzen and M.Shuey, “StackGhost: Hardware Facilitated Stack Protection,” Proc. of the 10th USENIX Security Symposium, Aug. 2001.
[6] K.Inoue, T.Ishihara, and K.Murakami, “Way-Predicting Set-Associative Cache for High Performance and Low Energy Consumption,” Proc. of the Int. Symp.on Low Power Electronics and Design, pp. 273--275, Aug. 1999.
[7] M.B.Kamble and K.Ghose, “Analytical Energy Dissipation Models For Low Power Caches,” Proc. of the Int. Symp. on Low Power Electronics and Design, pp.143--148, Aug. 1997
[8] C.Kim, D.Burger, and S.W.Keckler, “An Adaptive, Non-Uniform Cache Structure for Wire-Delay Dominated On-Chip Caches,” Proc. of the 10th Int. Conf.
on Architectural support for Programming Languages and Operating Systems, pp.211-222, Oct. 2002.
[9] J.Kin, M.Gupta, and W.H.Mngione-Smith, ”The Filter Cache: An Energy Efficient Memory Structure,” Proc.
of the 30th Int. Symp. on Microarchitecture, pp.184--193, Dec. 1997.
[10] R.B.Lee, D.K.Karig, J.P.McGregor, and Z.Shi,
“Enlisting Hardware Architecture to Thwart Malicious Code Injection,” Proc. of the Int. Conf. on Security in Pervasive Computing, Mar. 2003.
[11] M.D.Powell, A.Agarwal, T.N.Vijaykumar, B.Falsafi, and K.Roy, “Redicing Set-Associative Cache Energy via Way-Prediction and Selective Direct-Mapping,” Proc.
of the 34th Int. Symp. on Microarchitecture, pp.54--65, Dec. 2001.
[12] K.Scott and J.Davidson, “Safe Virtual Execution Using Software Dynamic Translation,” Proc. of the 18th Computer Security Applications Conference, Dec. 2002.
[13] D.Wagner, J.S.Foster, E.A.Brewer, and A.Aiken, “A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities,” Proc. of the Network and Distributed System Security Symposium, Feb. 2000.
[14] SimpleScalar Tool Sets, http://www.simplescalar.com/.
[15] SPEC(Standard Performance Evaluation Corporation, http://www.specbench.org/.
